#include "bst.h"


bst_t* creat_bst()
{
    bst_t* tree = malloc(sizeof(bst_t));
    if (tree == NULL) {
        return NULL;
    }
    memset(tree, 0, sizeof(bst_t));
    
    return tree;
}

int destroy_bst(bst_t* tree)
{
    bst_node_t* stack[10000];
    int top = -1;
    bst_node_t *cur;

    stack[++top] = tree->root;
    cur = tree->root->left;

    while (cur != NULL || top != -1 ) {
        while (cur != NULL){
            stack[++top] = cur;
            cur = cur->left;
        }
        
        cur = stack[top]->right;

        free(stack[top--]);
        tree->node_count--;
    }

    free(tree);
    return 0;
}


/**
 * @brief 计算节点是否是叶子节点
 * 
 * @param node 
 * @return 是返回1 不是返回0
 */
int is_leaf_node(bst_node_t* node)
{
    if (node == NULL) {
        return 0;
    }

    return node->left == NULL && node->right == NULL;
}


/**
 * @brief 创建节点
 * 
 * @param key: 键值
 * @return 新节点的指针
 */
bst_node_t* creat_node(int key)
{
    bst_node_t* new_node = malloc(sizeof(bst_node_t));
    if (new_node == NULL) {
        return NULL;
    }

    memset(new_node, 0, sizeof(bst_node_t));
    new_node->val = key;

    return new_node;
}


/*! 寻找目标节点，找到返回节点，没找到返回NULL */
/**
 * @brief   寻找目标节点，找到返回节点，没找到返回NULL
 * 
 * @param   root: 从此节点开始找
 * @param   key: 键值
 * @return  找到了返回目标节点，没找到返回NULL
 */
bst_node_t* search_node(bst_node_t* root, int key)
{
    bst_node_t* target = root;

    if (root == NULL) {
        return NULL;
    }

    while (target != NULL) {
        if( key < target->val) {
            target = target->left;
        } else if (key > target->val) {
            target = target->right;
        } else {
            return target;
        }
    }

    /* 没有目标节点 */
    return NULL;
}

/**
 * @brief 给树上插入一个新节点
 * 
 * @param tree 树
 * @param key 键值
 * @return 返回树本身
 */
bst_t* insert_node(bst_t* tree, int key)
{
    bst_node_t* cur;
    bst_node_t* new_node;

    new_node = creat_node(key);
    if (new_node == NULL) {
        return tree;
    }

    // 如果是空树，则创建根结点
    if (tree->root == NULL) {
        tree->root = new_node;
        tree->node_count++;
        return tree;
    }

    cur = tree->root;
    new_node->parent = cur;
    while (cur != NULL) {
        new_node->parent = cur;

        if (key < cur->val) {
            if (cur->left == NULL) {
                cur->left = new_node;
                break;
            } else {
                cur = cur->left;
            }
        } else if (key > cur->val) {
            if (cur->right == NULL) {
                cur->right = new_node;
                break;
            } else {
                cur = cur->right;
            }
        } else {
            free(new_node);
            return tree;
        }
    }

    tree->node_count++;
    return tree;
}



/**
 * @brief 删除叶子节点
 * 
 * @param tree 树
 * @param del 要删除的节点
 * @param flag 要删除的节点是其父节点的左节点还是右节点
 * @return int 
 */
static int delete_leaf_node(bst_t* tree, bst_node_t* del, int flag)
{
    bst_node_t* del_parent;


    if (del == NULL) {
        return -1;
    }

    /*! del == root，即要删除的叶子节点是根节点 */
    if (del == tree->root) {
        tree->root = NULL;
    } else {
        del_parent = del->parent;

        if (flag == LEFT_NODE) {
            del_parent->left = NULL;
        }

        if (flag == RIGHT_NODE) {
            del_parent->right = NULL;
        }
    }

    free(del);
    tree->node_count--;
    return 0;
}


/**
 * @brief Get the rsb min node object
 * 
 * @param root 
 * @param parentNode 
 * @return bst_node_t* 
 */
bst_node_t* get_rsb_min_node(bst_node_t* root, bst_node_t** parentNode)
{
    bst_node_t* cur;

    if (root == NULL) {
        *parentNode = NULL;
        return NULL;
    }

    *parentNode = root;
    cur = root->right;
    while (cur->left != NULL) {
        *parentNode = cur;
        cur = cur->left;
    }

    return cur;
}

/**
 * @brief 删除键值对应的节点
 * 
 * @param tree 
 * @param key 
 * @return int 
 */
int delete_node(bst_t* tree, int key)
{
    bst_node_t *del = NULL, *del_parent = NULL;
    bst_node_t *rsb_min_node = NULL, *rsb_min_node_parent = NULL;
    int flag;


    if (tree == NULL || tree->root == NULL) {
        return -1;
    }

    del = search_node(tree->root, key);
    if (del == NULL) {
        return 0;
    }
    /*! 根结点的父节点是空NULL */
    del_parent = del->parent;
    
    if (is_leaf_node(del)) { /*!< 叶子节点 */
        if (del == tree->root) { /*! 是父节点 */
            delete_leaf_node(tree, del, -1);
            return 0;
        } else { /*! 不是父节点 */
            /*! 计算节点是其父节点的左节点还是右节点 */
            flag = key < del_parent->val ? LEFT_NODE : RIGHT_NODE;
            delete_leaf_node(tree, del, flag);
            return 0;
        }
    } else if (del->left == NULL && del->right != NULL) { /*!< 删除节点的左孩子为空，右孩子不为空 */
        if (del == tree->root) { /*! 根结点 */
            tree->root = tree->root->right;
            tree->root->parent = NULL;
        } else {
            /*! 计算节点是其父节点的左节点还是右节点 */
            flag = key < del_parent->val ? LEFT_NODE : RIGHT_NODE;
            if (flag == LEFT_NODE) {
                del->right->parent = del->parent;
                del_parent->left = del->right;
            } else {
                del->right->parent = del->parent;
                del_parent->right = del->right;
            }
        }
    } else if(del->left != NULL && del->right == NULL) { /*!< 删除节点的右孩子为空，左孩子不为空 */
        if (del == tree->root) { /*! 根结点 */
            tree->root = tree->root->left;
            tree->root->parent = NULL;
        } else {
            /*! 计算节点是其父节点的左节点还是右节点 */
            flag = key < del_parent->val ? LEFT_NODE : RIGHT_NODE;
            if (flag == LEFT_NODE) {
                del->left->parent = del->parent;
                del_parent->left = del->left;
            } else {
                del->left->parent = del->parent;
                del_parent->right = del->left;
            }
        }
    } else { /*!< 删除节点的左右孩子都不为空 */
        rsb_min_node = get_rsb_min_node(del, &rsb_min_node_parent);
        if (del == tree->root) { /*! 根结点 */
            if (del->right->left == NULL) {
                rsb_min_node->left = tree->root->left;
                tree->root->left->parent = rsb_min_node;

                tree->root = rsb_min_node;
                tree->root->parent = NULL;
            } else {
                rsb_min_node_parent->left = rsb_min_node->right;
                if (rsb_min_node_parent->left == NULL) {
                    rsb_min_node->left = tree->root->left;
                    tree->root->left->parent = rsb_min_node;

                    rsb_min_node->right = tree->root->right;
                    tree->root->right->parent = rsb_min_node;

                    tree->root = rsb_min_node;
                    tree->root->parent = NULL;
                } else {
                    rsb_min_node_parent->left->parent = rsb_min_node_parent;

                    rsb_min_node->left = tree->root->left;
                    tree->root->left->parent = rsb_min_node;

                    rsb_min_node->right = tree->root->right;
                    tree->root->right->parent = rsb_min_node;

                    tree->root = rsb_min_node;
                    tree->root->parent = NULL;
                }
            }
        } else { /*!< 非根节点 */
            flag = key < del_parent->val ? LEFT_NODE : RIGHT_NODE;
            if (flag == LEFT_NODE) { /*! 要删除的节点是其父节点的左节点 */
                if (del == rsb_min_node_parent) {
                    rsb_min_node->parent = del->parent;
                    del->parent->left = rsb_min_node;

                    rsb_min_node->left = del->left;
                    del->left->parent = rsb_min_node;
                } else {
                    rsb_min_node_parent->left = rsb_min_node->right;
                    if (rsb_min_node_parent->left == NULL) {
                        rsb_min_node->left = del->left;
                        del->left->parent = rsb_min_node;

                        rsb_min_node->right = del->right;
                        del->right->parent = rsb_min_node;

                        del->parent->left = rsb_min_node;
                        rsb_min_node->parent = del->parent;
                    } else {
                        rsb_min_node_parent->left->parent = rsb_min_node_parent;

                        rsb_min_node->left = del->left;
                        del->left->parent = rsb_min_node;

                        rsb_min_node->right = del->right;
                        del->right->parent = rsb_min_node;

                        del->parent->left = rsb_min_node;
                        rsb_min_node->parent = del->parent;
                    }
                }
            }
            else { /*! 要删除的节点是其父节点的右节点 */
                if (del == rsb_min_node_parent)
                {
                    rsb_min_node->parent = del->parent;
                    del->parent->right = rsb_min_node;

                    rsb_min_node->left = del->left;
                    del->left->parent = rsb_min_node;
                } else {
                    rsb_min_node_parent->left = rsb_min_node->right;
                    if (rsb_min_node_parent->left == NULL) {
                        rsb_min_node->left = del->left;
                        del->left->parent = rsb_min_node;

                        rsb_min_node->right = del->right;
                        del->right->parent = rsb_min_node;

                        del->parent->right = rsb_min_node;
                        rsb_min_node->parent = del->parent;
                    } else {
                        rsb_min_node_parent->left->parent = rsb_min_node_parent;

                        rsb_min_node->left = del->left;
                        del->left->parent = rsb_min_node;

                        rsb_min_node->right = del->right;
                        del->right->parent = rsb_min_node;

                        del->parent->right = rsb_min_node;
                        rsb_min_node->parent = del->parent;
                    }
                }
            }
        }
    }

    free(del);
    tree->node_count--;
    return 0;
}


void infix(bst_node_t* root)
{
    if (root == NULL) {
        return;
    }

    infix(root->left);
    printf("%ld ", root->val);
    infix(root->right);
}

